/*
 * Implement pow(x, n).
 */
package com.xinpan.exercise;

/*do again*/
public class POW {
    public double pow(double x, int n) {
        // Start typing your Java solution below
        // DO NOT write main() function
        int m = Math.abs(n);
        
        double res = subPow(x, m/2);
        res *= res;
        if(m % 2 == 1)
            res *= x;
        
        if(n < 0)
        {
            if(res == 0)
                res = Double.MAX_VALUE;
            else
                res = 1/res;
        }
        return res;
    }
    
    public double subPow(double x, int m)
    {
        if(m == 0)
            return 1;
        else if(m == 1)
            return x;
        
        double res = subPow(x, m/2);
        if(res == 0)
            return 0;
        
        res *= res;
        if(m % 2 == 1)
            res *= x;
        return res;
    }
}
